package com.LeeCode;

/**
 * 统计重新排列后包含另一个字符串的子字符串数目 II
 */

public class Code3298 {
    public static void main(String[] args) {
        String s1 = "abcabc";
        String s2 = "abc";
        System.out.println(new Code3298().validSubstringCount(s1, s2));
    }

    public long validSubstringCount(String word1, String word2) {
        int[] target = new int[26];
        int total = 0;
        for (char c : word2.toCharArray()) {
            target[c - 'a']++;
            if (target[c - 'a'] == 1) total++;
        }

        long ans = 0;
        int right = 0, count = 0;
        int[] cnt = new int[26];
        char[] chars = word1.toCharArray();
        for (int left = 0; left < chars.length; left++) {
            while (right < chars.length && count < total) {
                cnt[chars[right] - 'a']++;
                if (cnt[chars[right] - 'a'] == target[chars[right] - 'a'])
                    count++;
                right++;
            }

            if (count == total) {
                ans += chars.length - right + 1;
            }

            cnt[chars[left] - 'a']--;
            if (cnt[chars[left] - 'a'] == target[chars[left] - 'a'] - 1) {
                count--;
            }
        }
        return ans;
    }
}
